package lc.Q200_250;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q210 {

    public static void main(String[] args) {
        Q210 q210 = new Q210();
        int[] order = q210.findOrder(6, new int[][]{
                new int[]{1, 0},
                new int[]{2, 0},
                new int[]{3, 1},
                new int[]{4, 2},
                new int[]{5, 3},
                new int[]{5, 4}
        });
        System.out.println(Arrays.toString(order));
    }

    private int[] visited;
    private int current;
    private boolean valid = true;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 首先构建图的边
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }
        visited = new int[numCourses];
        current = numCourses - 1;
        // 边构建好了后，开始访问
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            visit(edges, i, result);
        }
        if (!valid) {
            return new int[0];
        }
        return result;
    }

    private void visit(List<List<Integer>> edges, int index, int[] result) {
        if (!valid) {
            return;
        }
        if (visited[index] == 2) {
            return;
        }
        visited[index] = 1;
        List<Integer> integers = edges.get(index);
        for (Integer integer : integers) {
            // 如果未搜索过，则搜索
            if (visited[integer] == 0) {
                visit(edges, integer, result);
            }
            // 如果有未完成的，说明遇到还了
            else if (visited[integer] == 1) {
                valid = false;
                return;
            }
        }
        visited[index] = 2;
        result[current --] = index;
    }

}
